package E_2024;

import java.util.*;

/*
    一个XX 产品行销总公司，只有一个 boss，其有若干一级分销，一级分销又有若干二级分销，每个分销只有唯一的上级分销规定，每个月，下级分销需要将自己的总收入(自己的+下级上交的)每满 100 元上交 15 元给自己的上级.现给出一组分销的关系，和每个分销的收入，请找出 boss 并计算出这 boss 的收入。比如: 收入 100 元上交 15 元,收入 199 元(99 元不够 100)上交 15 元收入 200 元，上交 30 元。分销关系和收入:[I分销id 上级分销的Id 收入，[分销id 上级分销的id 收入]，[分销id 级分销的id 收入]]分销 ID 范围 0...65535
    收入范围: 0...65535,单位元
    提示: 输入的数据只存在 1个 boss，不存在环路
    输入描述
        第 1 行输入关系的总数量 N
        第 2 行开始，输入关系信息，格式: 分销 ID 上级分销 ID 收入
    输出描述
        boss 的ID 总收入
    补充说明
        给定的输入数据都是合法的，不存在重复
    示例1
        输入
            5
            1 0 100
            2 0 200
            3 0 300
            4 0 200
            5 3 200
        输出
            0 150
 */
public class E_100_14 {
    public static void main(String[] args) {
        Integer[][] s = new Integer[][]{{1,0,100},{2,0,200},{3,0,300},{4,0,200},{5,3,200}};
        System.out.println(Arrays.toString(ans(s)));
    }
    public static int[] ans(Integer[][] ts){
        // 元素集合，不再该集合内的就是boss
        Map<Integer,Integer> patentId = new HashMap<>();
        for (Integer[] t : ts) {
            patentId.put(t[1], 0);
        }
        /* 判断当前元素的父集是否在patentId内，不在内的就是bossId
        */
        int bossId = 0;
        Map<Integer, List<Integer[]>> ch = new HashMap<>();
        for (Integer[] tt : ts) {
            // 判断是否是bossId
            if (!patentId.containsKey(tt[1])) bossId = tt[1];
            // 将当前元素归到对应父集中
            List<Integer[]> orDefault = ch.getOrDefault(tt[1], new ArrayList<>());
            orDefault.add(tt);
            ch.put(tt[1],orDefault);
        }
        return new int[]{bossId,xx(ch,bossId)};
    }
    public static int xx(Map<Integer, List<Integer[]>> ch, Integer ii){
        List<Integer[]> ss = ch.get(ii);
        int price = 0;
        for (Integer[] child : ss) {
            if (ch.containsKey(child[0])){
                price += xx(ch,child[0]);
            }
            price += child[2];
        }
        return price / 100 * 15;
    }
}
